package cxydmmszl.chapter08.t139;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 * 数组中未出现的最小正整数
 * <li style="color: red;">Desc</li>
 * 给定一个无序数组arr，找到数组中未出现的最小正整数。<br/><br/>
 * 输入描述：<br/>
 * 第一行为一个整数 N。表示数组长度。<br/>
 * 接下来一行 N 个整数表示数组内的数<br/><br/>
 * 输出描述：<br/>
 * 输出一个整数表示答案
 * <li style="color: red;">Link</li> CD39
 *
 * @author habitplus
 * @since 2021-09-07 09:52
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bf.readLine());
        int[] arr = new int[n];
        String[] ss;
        ss = bf.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(ss[i]);
        }
        bf.close();

        int ans = missMinNum(arr);
        System.out.println(ans);
    }

    public static int missMinNum(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int l = 0;
        int r = arr.length;

        while (l < r) {
            if (arr[l] == l + 1) {
                l++;
            } else if (arr[l] <= l || arr[l] > r || arr[arr[l] - 1] == arr[l]) {
                arr[l] = arr[--r];
            } else {
                swap(arr, l, arr[l] - 1);
            }
        }

        return l + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        if (i == j || arr[i] == arr[j]) return;
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}
